package edu.whu.rose.clock.ssql.index;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Date;
import java.util.HashMap;
import java.util.Iterator;

import edu.whu.rose.clock.ssql.graph.RRadiusSubGraph;
import edu.whu.rose.clock.ssql.graph.SubGraphDB;
import edu.whu.rose.clock.ssql.util.ExpandableIntArray;
import edu.whu.rose.clock.ssql.util.SequentialIntArray;

public class RelationshipMatrix {

	private final int rank;
	private int totalNumOfEdges;
	
	private HashMap<Integer,RelationshipNode> rowHeads;
	private HashMap<Integer,RelationshipNode> columnHeads;
	
	private SubGraphDB sgdb;
	
	public RelationshipMatrix(int rank) {
		this.rank = rank;
		this.rowHeads = new HashMap<Integer,RelationshipNode>();
		this.columnHeads = new HashMap<Integer,RelationshipNode>();
		this.fillDiagonalNodes();
	}
	
	public static void main(String[] args) {
		
		RelationshipMatrix rm = new RelationshipMatrix(1754297);
		rm.fillDiagonalNodes();
		rm.load("graph/edge.txt");
		SubGraphDB sgdb = new SubGraphDB();
		sgdb.initEnv();
		sgdb.openDB();
		rm.setSgdb(sgdb);
		Date start = new Date();
		rm.multiply(rm);
		Date end = new Date();
		System.out.println((end.getTime() - start.getTime()) + "ms");
		sgdb.closeDB();
//		RelationshipMatrix rm = new RelationshipMatrix(4);
//		rm.fillDiagonalNodes();
//		RelationshipMatrix orm = new RelationshipMatrix(4);
//		orm.fillDiagonalNodes();
//		rm.load();
//		orm.load();
//		rm = rm.multiply(orm);
//		rm = rm.multiply(orm);
		
//		Iterator<Integer> it = rm.rowHeads.keySet().iterator();
//		while (it.hasNext()) {
//			RelationshipNode rn = rm.rowHeads.get(it.next());
//			int row = rn.getRow();
//			System.out.print((row + 1) + " : ");
//			while (rn != null) {
//				int column = rn.getColumn();
//				System.out.print((column + 1) + " ");
//				
//				rn = rn.getNextNodeInSameRow();
//			}
//			System.out.println();
//		}
		
//		try {
//			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//			while (true) {
//				System.out.println("Please input query:");
//				String statement = br.readLine().trim();
//				if (!statement.equals("exit")) {
//					String[] nums = statement.split(",");
//					System.out.println(rm.getDBLP(new Integer(nums[0].trim()).intValue(), new Integer(nums[1].trim()).intValue()));
//				}
//				else {
//					break;
//				}
//			}
//			br.close();
//		}
//		catch (IOException ex) {
//			ex.printStackTrace();
//		}
	}
	
	public void load() {
		this.insert(0, 2, null);
		this.insert(2, 3, null);
		this.insert(3, 1, null);
	}
	
	public int load(String dataFile) {
		try {
			BufferedReader br = new BufferedReader(new FileReader(dataFile));
			while (br.ready()) {
				String line = br.readLine().trim();
				String edge = line.substring(line.lastIndexOf(" ") + 1);
				int pos1 = edge.indexOf("-->");
				int pos2 = edge.indexOf(":");
				if (pos1 == -1 || pos2 == -1) {
					System.err.println("Found a wrong edge: " + edge);
					continue;
				}
				int row = new Integer(edge.substring(0, pos1)).intValue() - 1;
				int column = new Integer(edge.substring(pos1 + 3, pos2)).intValue() - 1;
				String relationship = edge.substring(pos2 + 1);
				
				if (relationship != null) {
					this.insert(row, column, new String[]{relationship});
					
					if (relationship.equals("write")) {
						this.insert(column, row, new String[]{"writtenBy"});
					}
					else if (relationship.equals("edit")) {
						this.insert(column, row, new String[]{"editedBy"});
					}
					else if (relationship.equals("publish")) {
						this.insert(column, row, new String[]{"publishedBy"});
					}
					else if (relationship.equals("cite")) {
						this.insert(column, row, new String[]{"citedBy"});
					}
					else if (relationship.equals("www")) {
						this.insert(column, row, new String[]{"owner"});
					}
					else if (relationship.equals("school")) {
						this.insert(column, row, new String[]{"student"});
					}
					else if (relationship.equals("inproceedings")) {
						this.insert(column, row, new String[]{"have"});
					}
					else if (relationship.equals("incollection")) {
						this.insert(column, row, new String[]{"have"});
					}
					else {
						System.err.println("Unknown Relationship: " + relationship);
					}
				}
				else {
					System.err.println("Null Relationship: " + row + "/" + column);
				}
			}
			System.out.println("Loading finished");
			br.close();
		}
		catch (IOException ex) {
			ex.printStackTrace();
		}
		return totalNumOfEdges;
	}
	
	public void rowSearch(int row, int length, RRadiusSubGraph rrsg) {
		RelationshipNode rn = rowHeads.get(new Integer(row));
		SequentialIntArray sia = new SequentialIntArray();
		
		while (rn != null) {
			int column = rn.getColumn();
			RelationshipNode rn2 = this.getRowHeads().get(new Integer(column));
			
			while (rn2 != null) {
				sia.insert(rn2.getColumn() + 1);
				rn2 = rn2.getNextNodeInSameRow();
			}
			
			rn = rn.getNextNodeInSameRow();
		}
		
		rrsg = new RRadiusSubGraph(row, sia.getArray());
	}
	
	public RRadiusSubGraph rowSearch(int row, int length) {
		RelationshipNode rn = rowHeads.get(new Integer(row));
		SequentialIntArray sia = new SequentialIntArray();
		
		while (rn != null) {
			int column = rn.getColumn();
			RelationshipNode rn2 = this.getRowHeads().get(new Integer(column));
			
			while (rn2 != null) {
				sia.insert(rn2.getColumn() + 1);
				rn2 = rn2.getNextNodeInSameRow();
			}
			
			rn = rn.getNextNodeInSameRow();
		}
		
		return new RRadiusSubGraph(row + 1, sia.getArray());
	}
	
	public RRadiusSubGraph[] multiply(RelationshipMatrix multiplicand) {
		if (this.rank == multiplicand.rank) {
			RRadiusSubGraph[] result = new RRadiusSubGraph[rank];
			
			if (this.rowHeads.keySet().size() == rank) {
				Iterator<Integer> it = this.rowHeads.keySet().iterator();
				while (it.hasNext()) {
					RelationshipNode rn = rowHeads.get(it.next());
					int row = rn.getRow();
					SequentialIntArray sia = new SequentialIntArray();
					
					while (rn != null) {
						int column = rn.getColumn();
						RelationshipNode rn2 = multiplicand.getRowHeads().get(new Integer(column));
						
						while (rn2 != null) {
							sia.insert(rn2.getColumn() + 1);
							rn2 = rn2.getNextNodeInSameRow();
						}
						
						
						rn = rn.getNextNodeInSameRow();
					}
					
					RRadiusSubGraph rrsg = new RRadiusSubGraph(row, sia.getArray());
//					result[row] = rrsg;
//					this.saveToDB(row, rrsg);
				}
				
				return result;
			}
			
		}
		
		return null;
	}
	
	public RRadiusSubGraph genSubGraph(int row) {
		RelationshipNode rn = rowHeads.get(new Integer(row));
		SequentialIntArray sia = new SequentialIntArray();
		
		while (rn != null) {
			int column = rn.getColumn();
			RelationshipNode rn2 = this.getRowHeads().get(new Integer(column));
			
			while (rn2 != null) {
				sia.insert(rn2.getColumn() + 1);
				rn2 = rn2.getNextNodeInSameRow();
			}
			
			
			rn = rn.getNextNodeInSameRow();
		}
		
		return new RRadiusSubGraph(row, sia.getArray());
	}
	
//	public ArrayList<String> allPaths() {
//		ArrayList<String> result = new ArrayList<String>();
//		
//		ListIterator<Integer> li = rows.listIterator();
//		int index = 0;
//		while (li.hasNext()) {
//			int row = li.next().intValue();
//			int column = columns.get(index).intValue();
//			index++;
//			result.add(this.singlePath(row, column));
//		}
//		
//		return result;
//	}
	
	public String[] power(int row, int column) {
		String[] newRelationships = new String[0];
		
		Integer r = new Integer(row);
		Integer c = new Integer(column);
		
		RelationshipNode rowIndex = this.rowHeads.get(r);
		RelationshipNode columnIndex = this.columnHeads.get(c);
		
		while (rowIndex != null && columnIndex != null) {
			if (rowIndex.getColumn() < columnIndex.getRow()) {
				rowIndex = rowIndex.getNextNodeInSameRow();
			}
			else if (rowIndex.getColumn() > columnIndex.getRow()) {
				columnIndex = columnIndex.getNextNodeInSameColumn();
			}
			else {
				String[] temp = this.mergeRelationships(rowIndex.getRelationships(), columnIndex.getRelationships());
				if (temp != null) {
					newRelationships = this.mergeArray(newRelationships, temp);
				}
				rowIndex = rowIndex.getNextNodeInSameRow();
				columnIndex = columnIndex.getNextNodeInSameColumn();
			}
		}
		
		return newRelationships;
	}
	
	public void insert(int row, int column, String[] relationships) {
		if (row > rank - 1 | column > rank - 1 | row < 0 | column < 0) {
			System.out.println("Error: insert in position (" + row + "," + column + ")");
			return;
		}
		RelationshipNode newNode = new RelationshipNode(row, column, relationships);
		Integer r = new Integer(row);
		Integer c = new Integer(column);
		RelationshipNode rowHead = this.rowHeads.get(r);
		RelationshipNode columnHead = this.columnHeads.get(c);
		if (rowHead == null) {
			this.rowHeads.put(r, newNode);
		}
		else {
			if (rowHead.getColumn() > column) {
				newNode.setNextNodeInSameRow(rowHead);
				this.rowHeads.put(r, newNode);
			}
			else if (rowHead.getColumn() < column) {
				RelationshipNode rd = null;
				for (rd = rowHead; rd.getNextNodeInSameRow() != null && 
				rd.getNextNodeInSameRow().getColumn() < column; rd = rd.getNextNodeInSameRow());
				if (rd.getNextNodeInSameRow() == null) {
					rd.setNextNodeInSameRow(newNode);
				}
				else {
					if (rd.getNextNodeInSameRow().getColumn() == column) {
						rd.getNextNodeInSameRow().setRelationships(this.mergeArray(rd.getRelationships(), relationships));
						System.out.println("Notice: insert in same position (" + row + "," + column + ")");
						return;
					}
					else {
						newNode.setNextNodeInSameRow(rd.getNextNodeInSameRow());
						rd.setNextNodeInSameRow(newNode);
					}
				}
			}
			else {
				rowHead.setRelationships(this.mergeArray(rowHead.getRelationships(), relationships));
				System.out.println("Notice: insert in same position (" + row + "," + column + ")");
				return;
			}
		}
		if (columnHead == null) {
			this.columnHeads.put(c, newNode);
		}
		else {
			if (columnHead.getRow() > row) {
				newNode.setNextNodeInSameColumn(columnHead);
				this.columnHeads.put(c, newNode);
			}
			else {
				RelationshipNode rd = null;
				for (rd = columnHead; rd.getNextNodeInSameColumn() != null && 
				rd.getNextNodeInSameColumn().getRow() < row; rd = rd.getNextNodeInSameColumn());
				if (rd.getNextNodeInSameColumn() == null) {
					rd.setNextNodeInSameColumn(newNode);
				}
				else {
					newNode.setNextNodeInSameColumn(rd.getNextNodeInSameColumn());
					rd.setNextNodeInSameColumn(newNode);
				}
			}
		}
		if (row != column) {
			totalNumOfEdges++;
		}
	}
	
//	private String[] appendToArray(String[] arr, String str) {
//		String[] result = new String[arr.length + 1];
//		for (int i = 0; i < arr.length; i++) {
//			result[i] = arr[i];
//		}
//		result[arr.length] = str;
//		return result;
//	}
//	
	private String[] mergeArray(String[] arr1, String[] arr2) {
		if (arr1 == null || arr2 == null) {
			return null;
		}
		String[] result = new String[arr1.length + arr2.length];
		for (int i = 0; i < arr1.length; i++) {
			result[i] = arr1[i];
		}
		for (int i = 0; i < arr2.length; i++) {
			result[i + arr1.length] = arr2[i];
		}
		return result;
	}
	
//	public String getDBLP(int row, int column) {
//		String relationship = null;
//		if (row > column) {
//			relationship = this.get(column, row);
//			return "inversed: " + relationship;
//		}
//		else {
//			return this.get(row, column);
//		}
////		if (relationship.equals("author")) {
////			return "write";
////		}
////		else if (relationship.equals("write")) {
////			return "author";
////		}
////		else if (relationship.equals("edit")) {
////			return "editor";
////		}
////		else if (relationship.equals("editor")) {
////			return "edit";
////		}
////		else if (relationship.equals("publish")) {
////			return "publisher";
////		}
////		else if (relationship.equals("publisher")) {
////			return "publish";
////		}
////		else if (relationship.equals("citedBy")) {
////			return "cite";
////		}
////		else if (relationship.equals("cite")) {
////			return "citedBy";
////		}
////		else if (relationship.equals("www")) {
////			return "owner";
////		}
////		else if (relationship.equals("owner")) {
////			return "www";
////		}
////		else if (relationship.equals("school")) {
////			return "student";
////		}
////		else if (relationship.equals("student")) {
////			return "school";
////		}
////		else if (relationship.equals("inproceedings")) {
////			return "embody";
////		}
////		else if (relationship.equals("embody")) {
////			return "inproceedings";
////		}
////		else if (relationship.equals("incollection")) {
////			return "have";
////		}
////		else if (relationship.equals("have")) {
////			return "incollection";
////		}
////		else {
////			System.out.println("Unknown Relationship: " + relationship);
////			return null;
////		}
//		
//	}
	
	public String[] mergeRelationships(String[] rels1, String[] rels2) {
		ArrayList<String> result = new ArrayList<String>();
		
		if (rels1 != null && rels2 != null) {
			for (int i = 0; i < rels1.length; i++) {
				for (int j = 0; j < rels2.length; j++) {
					if (rels1[i].equals("#")) {
						result.add(rels2[j]);
					}
					else {
						result.add(rels1[i] + (rels2[j].equals("#") ? "" : "/" + rels2[j]));
					}
				}
			}
			return result.toArray(new String[result.size()]);
		}
		return null;
	}
	
//	public void saveToDB(int key, RRadiusSubGraph value) {
//		try {
//			if (sgdb != null) {
//				sgdb.insertRawSG(key, value);
//			}
//		}
//		catch (DatabaseException ex) {
//			ex.printStackTrace();
//		}
//	}

	public String[] get(int row, int column) {
		if (row < column) {
			Integer c = new Integer(column);
			RelationshipNode columnHead = this.columnHeads.get(c);
			if (columnHead == null) {
				return null;
			}
			if (columnHead.getRow() == row) {
				return columnHead.getRelationships();
			}
			else if (columnHead.getRow() > row) {
				return null;
			}
			else {
				RelationshipNode rd = null;
				for (rd = columnHead; rd.getNextNodeInSameColumn() != null && 
				rd.getNextNodeInSameColumn().getRow() < row; rd = rd.getNextNodeInSameColumn());
				if (rd.getNextNodeInSameColumn() == null || rd.getNextNodeInSameColumn().getRow() > row) {
					return null;
				}
				else {
					return rd.getNextNodeInSameColumn().getRelationships();
				}
			}
		}
		else {
			Integer r = new Integer(row);
			RelationshipNode rowHead = this.rowHeads.get(r);
			if (rowHead == null) {
				return null;
			}
			if (rowHead.getColumn() == column) {
				return rowHead.getRelationships();
			}
			else if (rowHead.getRow() > row) {
				return null;
			}
			else {
				RelationshipNode rd = null;
				for (rd = rowHead; rd.getNextNodeInSameRow() != null && 
				rd.getNextNodeInSameRow().getColumn() < column; rd = rd.getNextNodeInSameRow());
				if (rd.getNextNodeInSameRow() == null || rd.getNextNodeInSameRow().getColumn() > column) {
					return null;
				}
				else {
					return rd.getNextNodeInSameRow().getRelationships();
				}
			}
		}
	}
	
	public String appendRelationships(String rel1, String rel2) {
		String result = rel1;
		String[] paths1 = rel1.split("\\+");
		String[] paths2 = rel2.split("\\+");
		for (int i = 0; i < paths2.length; i++) {
			boolean contain = false;
			for (int j = 0; j < paths1.length; j++) {
				if (paths1[j].equals(paths2[i])) {
					contain = true;
					break;
				}
			}
			if (!contain) {
				result += paths2[i] + "+";
			}
		}
		return result;
	}
	
	public void fillDiagonalNodes() {
		for (int i = 0; i < rank; i++) {
			this.insert(i, i, new String[]{"#"});
		}
	}
	
//	public void loadPoweredMatrix(BufferedReader rowReader, BufferedReader columnReader) {
//		rows.clear();
//		columns.clear();
//		System.gc();
//		try {
//			for (int i = 0; i < from; i++) {
//				rowReader.readLine();
//				columnReader.readLine();
//			}
//			for (int i = from; i < to; i++) {
//				while () {
//					String line = rowReader.readLine().trim();
//					rows.add(this.parseSN(line));
//				}
//				while () {
//					String line = columnReader.readLine().trim();
//					columns.add(this.parseSN(line));
//				}
//			}
//			
//			rowReader.close();
//			columnReader.close();
//		}
//		
//		if (rows.size() != columns.size()) {
//			System.err.println("Error: loading powered matrix failed");
//		}
//	}
	
	public Integer parseSN(String line) {
		int pos = line.indexOf("e");
		
		String str1 = line.substring(0, pos);
		String str2 = line.substring(line.length() - 1);
		double d1 = new Double(str1).doubleValue();
		double d2 = new Double(str2).doubleValue();
		d1 = d1 * Math.pow(10.0D, d2);
		return new Integer(new Double(d1).intValue());
		
		
		
//		int i = pos - 1;
//		for (; i > 0; i--) {
//			if (!line.subSequence(i, i + 1).equals("0")) {
//				break;
//			}
//		}
//		String result = line.substring(0, i + 1);
//		pos = result.indexOf(".");
//		result = result.substring(0, pos) + result.substring(pos + 1);
//		return new Integer(result);
	}
	
	public int[] getColumns(int row) {
		RelationshipNode rowHead = rowHeads.get(new Integer(row));
		if (rowHead == null) {
			return null;
		}
		else {
			ExpandableIntArray eia = new ExpandableIntArray();
			if (rowHead.getColumn() > row) {
				eia.add(rowHead.getColumn());
			}
			for (RelationshipNode rn = rowHead.getNextNodeInSameRow(); rn != null; 
			rn = rn.getNextNodeInSameRow()) {
				if (rn.getColumn() > row) {
					eia.add(rn.getColumn());
				}
			}
			return eia.toArray();
		}
	}

	public HashMap<Integer, RelationshipNode> getRowHeads() {
		return rowHeads;
	}

	public HashMap<Integer, RelationshipNode> getColumnHeads() {
		return columnHeads;
	}

	public int getRank() {
		return rank;
	}

	public void setSgdb(SubGraphDB sgdb) {
		this.sgdb = sgdb;
	}

}
